#######################################################
# The class of general graphs 
# Author: moonho.hwang@gmail.com
#   Date: Oct.19.2011
#######################################################
S_id = 'id'   # symbol for id 
S_dst = 'dst' # symbol for destination 
S_src = 'src' # symbol for source 
S_type = 'type' # symbol for type

#S_hide_keys = 'hide_keys'

from XSY.hashdict import *
from XSY.Base import *

class Graph:
   """
A general graph class
   V: a dictionary of vertices  V[v]={(attr, value)}
   E: a set of edges, where e in E, src(e) and dst(e) are source and destination of e    
  FE: a dictionary of  forward edges FE[srcv][{e in E: src(e)=srcv}]
  BE: a dictionary of backward edges BE[dstv][{e in E: dst(e)=dstv}]
   """
   def __init__(self):
      ''' constructor '''
      self.V = dict()  #  V: a dictionary of vertices V[v][attr]
      self.E = set()   #  E: a set of edges
      self.FE = dict() # FE: a dictionary of forward edges  FE[srcv][{e in E: src(e)=srcv}]
      self.BE = dict() # BE: a dictionary of backward edges BE[dstv][{e in E: dst(e)=dstv}]

   def addVtx(self, v, attr={}):
      """add a vertex v and attributes attr"""
      if v in self.V.keys():
        print "Warning: " + str(v) +" is already exist"
      else:
        self.V[v]=attr 
      #print self.V # for debuggin 

   def getVtxs(self, v_checker=None):
      '''get {v in V: v_checker(self, v) == True} '''
      return Graph.filterV(self, self.V, v_checker)

      #answer =set() 
      #for v in self.V.keys():
      #   if v_checker == None or v_checker(self, v): answer.add(v)
      #return answer

   @staticmethod
   def filterV(G, V, v_checker):
      answer = set()
      for v in V:
         if v_checker == None or v_checker(G, v): 
            answer.add(v)
      return answer

   def removeVtx(self, v):
       '''remove vtx v from V and all edges incoming to/outgoin from v'''
       if v in self.V.keys():
           self.V.pop(v)

       self.removeInEdges(v)
       self.removeOutEdges(v)

   def getVattribute(self, v, aname):
      '''Get the value of attribute <i>aname</i> of the vertx <i>v</i>.
         return None if there is no attribute on (v, aname). '''
      if v not in self.V: return None  
      if aname not in self.V[v]: return None
      return self.V[v][aname]

   def getVattributes(self, v):
      '''
      Get all attributes of vertex <i>v</i>
      return self.V[v] if v in self.V; otherwise, return {} which is the empty dictionary. '''
      if v in self.V: return self.V[v] 
      else: return {} # {} is the empty dictionary 
   
   def addEdge(self, src_v, dest_v, attr={}):
      ''' Add an edge (sr_v, dest_v, attr).
      Raises an exception if src_v or dest_v is not a registered vertex.
      return false if the edge is pre-existing, otherwise return true.'''
      if src_v not in self.V: raise NameError("vtx "+str(src_v)+" is not registered.")
      if dest_v not in self.V: raise NameError("vtx "+str(dest_v)+" is not registered.")         
      
      if src_v not in self.FE: self.FE[src_v]=set()
      edge = hashdict(attr) # copy destination edge de
      edge[S_dst]=dest_v # add attribute S_dst:dest_v in de
      edge[S_src]=src_v # add attribute S_src:src_v in se
      
      self.E.add(edge)  # register in E

      if edge in self.FE[src_v]:
         print "Warning: " + str(edge) + " is already exists!"
         return None
      else :
         self.FE[src_v].add(edge)
		
         if dest_v not in self.BE: self.BE[dest_v]=set()
         #do not creat it again ! comment it out #e = hashdict(attr) # copy source edge se
         if edge in self.BE[dest_v]:
            print "Warning: " + str(edge) + " is already exists!"
            return None
         else :
            self.BE[dest_v].add(edge)

      return edge

   def getEdges(self, src, dest, e_checker=None):
      '''{e in E:src(e)=src if src!=None, dst(e)=dest if dest!=None, e_checker(self,e)==True if e_checker != None}'''
      answer = set()
      for e in self.E:
        if (src == None or e[S_src] == src) and (dest == None or e[S_dst] == dest) and \
           (e_checker == None or e_checker(self, e)):
           answer.add(e)
      return answer 

   def removeEdgeFromFE(self, e):
      '''remove e from self.FE'''
      src_v = e[S_src]
      if src_v in self.FE.keys(): # remove e from FE
         self.FE[src_v].remove(e)
         if len(self.FE[src_v])==0: del self.FE[src_v]

   def removeEdgeFromBE(self, e):
      '''remove e from self.BE'''
      dest_v = e[S_dst]
      if dest_v in self.BE.keys():# remove e from BE
         self.BE[dest_v].remove(e)
         if len(self.BE[dest_v])==0: del self.BE[dest_v]

   def remove_edge(self, e):
      '''remove e from E, FE, and BE'''
      self.E.remove(e)         # remove e from E
      self.removeEdgeFromFE(e) # remove e from FE
      self.removeEdgeFromBE(e) # remove e from BE

   def removeEdge(self, src_v, dest_v, e_checker=None):
      '''remove e in getEdges(src_v, dest_v, e_checker) from FE, BF, and E'''
      for e in self.getEdges(src_v, dest_v, e_checker):
          self.remove_edge(e)

   def removeOutEdges(self, src_v, e_checker=None):
      '''remove e in getEdges(src_v, None, e_checker) from FE, BF, and E'''
      for e in self.getEdges(src_v, None, e_checker):
         self.remove_edge(e)
 
   def removeInEdges(self, dest_v, e_checker = None):
      '''remove e in getEdges(None, dest_v, e_checker) from FE, BF, and E'''
      for e in self.getEdges(None, dest_v, e_checker):
         self.remove_edge(e)

   def removeEdges(self, e_checker=None):
      '''remove e in getEdges(None, None, e_checker) from FE, BF, and E'''
      for e in self.getEdges(None, None, e_checker):
         self.remove_edge(e)

   def inE(self, to_v, e_checker=None):
      '''{e in E: dest(e)=to_v, e_checker(self,e)==True}'''
      if to_v not in self.BE: return set()
      E = set()
      for edge in self.BE[to_v]: 
         if e_checker==None or e_checker(self, edge): 
            E.add(edge)
      return E

   def inV(self, to_v, e_checker=None):
      '''{src(e) in V: e in inE(to_v, e_checker)}'''
      V = set()
      for se in self.inE(to_v, e_checker):
         if S_src in se.keys():
            V.add(se[S_src])
      return V

   def outE(self, from_v, e_checker=None):
      '''{e in E: src(e)=from_v, e_checker(self,e)==True}'''
      if from_v not in self.FE: 
         return set()
      E = set()
      for edge in self.FE[from_v]: 
         if e_checker == None or e_checker(self, edge) : 
            E.add(edge)
      return E

   def outV(self, from_v, e_checker=None):
      '''{dest(e) in V: e in outE(from_v,e_checker)}'''
      V = set()
      for edge in self.outE(from_v, e_checker):
         if S_dst in edge.keys():
            V.add(edge[S_dst])
      return V

   def tinV(self, to_v, e_checker=None):
      '''Get the set of all transtive input vertices of to_v in terms of edge type etype. '''
      answer = self.inV(to_v, e_checker)
      tmp = set()
      for v in answer:
         for w in self.tinV(v, e_checker): 
            tmp.add(w) 
      return answer.union(tmp)

   def toutV(self, from_v, e_checker=None):
      '''Get all transtive output vertices of from_v in terms of edge type etype. '''
      answer = self.outV(from_v, e_checker)
      tmp = set()
      for v in answer:
         for w in self.toutV(v, e_checker): 
            tmp.add(w) 
      return answer.union(tmp)

   def vtx2str(self,v):
      '''make a string from a vertex v'''
      return str(v)+","+dict_to_s(self.getVattributes(v))

   def vtxs2str(self):
      '''return a string of all vertices together with their attributes.'''
      strn = "\n########### Vertices, |V|=%d #############\n"%len(self.V)
      for v in sorted(self.V.iterkeys()): #Str.V:
         strn += self.vtx2str(v) + "\n"

      return strn
	#End of PrintVtxs method
   
   def edge2str(self, de):
      '''make a string from a directed edge de'''
      strn = ""
      src = de[S_src]
      if S_dst in de: dest = de[S_dst]
      edge = dict(de); del edge[S_dst]; del edge[S_src]
      if len(edge)>0 :
          strn += str(src)+" -[ "+dict_to_s(edge)+" ]-> "+str(dest)
      else:
          strn += str(src)+"--> "+str(dest)
      return strn

   def edges2str(self):
      '''return a string of all edges together with their attributes. '''
      strn = "\n############### Edges ###############\n"
      nE = 0
      for src in sorted(self.FE.keys()):
         for de in sorted(self.FE[src], key=lambda e: str(e[S_dst])):
            nE += 1
            strn += self.edge2str(de) + "\n"
      strn += "\n############### |E|=%d ###############\n"%nE
      return strn
   #End of Printedges2str

   def lenOfE(self):
      '''get length of E'''
      return len(self.E)

   def __str__(self):
      '''converting the class into a string. '''
      return self.vtxs2str() + self.edges2str()

   def __eq__(self, other):
      '''check if self == other'''
      if isinstance(other, Graph): 
         return  self.V == other.V and self.E == other.E
      else: 
         return False

# end of Graph class

########### built-in testing codes ################
if __name__ == '__main__':
    g = Graph()
    print g.__doc__
    g.addVtx(1, {'value':111})
    g.addVtx(2)
    g.addVtx(3)
    g.addEdge(1, 2, {S_type:'precedence', 'time': 10})
    g.addEdge(1, 2, {S_type:'precedence', 'cost': 100})
    g.addEdge(2, 3, {S_type:'precedence', 'cost': 100})

    print g
